第五讲 凸集及其分离
标准的最优化问题
标准的最优化问题：在标量约束\(G(x) \leq c\) 下选择向量\(x\) 以最大化\(F(x)\)。
等值线：对于一个多变量函数\(F(x)\) 而言，使得函数值等于\(c\) 的所有可能的向量\(x\) 共同构成一条等值线，对应优化问题中的约束条件。e.g. 预算约束线，等利润线，无差异曲线
上等值集：所有满足\(F(x) \geq v\) 的向量\(x\) 共同构成的集合
下等值集：所有满足\(G(x) \leq c\) 的向量\(x\) 共同构成的集合
凸集的分离性质
凸集(convex set)
定义： 对于\(n\) 维空间中的点集\(S\) 而言，如果给定\(S\) 中的任意两点\(x^a = (x_1^a, \cdots, x_n^a)\) 和\(x^b = (x_1^b, \cdots, x_n^b)\) 以及闭区间\([0,1]\)中的任意实数\(\theta\)，点\(\theta x^a + (1-\theta)x^b\) 也在点集\(S\) 中，那么称点集\(S\) 是凸的(convex)。
生产函数的下等值集是凸集，意味着什么？
效用函数的上等值集是凸集，意味着什么？
凸函数
定义1（从函数出发）： 如果一个函数\(G(x)\)满足，对于所有的\(x^a, x^b\)和任意\(\theta \in [0,1]\)，都有 \[ G(\theta x^a + (1 - \theta)x^b) \leq \theta G(x^a) + (1 - \theta)G(x^b) \] 则称其为凸函数(convex function)。
反之，若一个函数\(F(x)\)满足 \[ F(\theta x^a + (1 - \theta)x^b) \geq \theta F(x^a) + (1 - \theta)F(x^b) \] 则称其为凹函数(concave function)。
凹函数
拟凸函数
从代数上看，集合\(G(x)\leq c\) 是凸集意味着： \[ G(x^a) \leq c , G(x^b) \leq c \Rightarrow G(\theta x^a + (1 - \theta) x^b) \leq c \]
如果其中一个端点的值恰好等于\(c\) 时，这个条件又可以表述为\(\forall x^a, x^b , \theta \in[0,1]\)： \[ G(\theta x^a + (1 - \theta) x^b) \leq max(G(x^a), G(x^b)) \]
我们称满足上述条件的函数为拟凸函数(quasi convex function)。
反之，如果函数\(F(x)\)满足 \[ F(\theta x^a + (1 - \theta) x^b) \geq min(F(x^a), F(x^b)) \] 则称其为拟凹函数(quasi concave function)。
内点与边界点
内点：如果存在点\(x^0\) 的邻域\(B(x^0, \delta)\) 包含于集合\(S\)，则称点\(x^0\) 是集合\(S\) 的一个内点(inner point)
边界点：如果一个点\(x^1\) 既不是集合\(S\)的内点，也不是集合\(S\) 的补集的内点，则称点\(x^1\) 是集合\(S\)的一个边界点(boundary points)。换言之，如果一个点\(x^1\)是集合\(S\) 的边界点，那么其任意邻域内，都既存在属于\(S\)的点，也存在不属于\(S\)的点
分散化下的局部失灵
分离定理
如果A和B为两个没有公共内点的凸集，且至少有一个集合有一个非空内点，那么我们总可以找到一个非零向量\(p\)和一个数\(b\)，使得超平面\(px = b\)分离这两个集合，或：
\[ px \begin{cases} \leq b, & \forall x \in A \\ \geq b, & \forall x \in B \end{cases} \]
分离角度的最优化定理
给定拟凹函数\(F\)和拟凸函数\(G\)，点\(\bar{x}\)在满足约束条件\(G(x) \leq c\)下使得\(F(x)\)最大，当且仅当存在一个非零向量\(p\)，使得：
\(\bar{x}\)在满足\(G(x) \leq c\)下最大化\(px\)
\(\bar{x}\)在满足\(F(x) \geq \bar{v}\)下最小化\(px\)
经济学解释
假定\(x\)为生产-消费向量，约束反映了资源的有限性，目标函数为效用函数。\(p\)理解为产出的价格向量，那么上述定理意味着：
寻求产出价格最大化的企业家会生产出最优产量\(\bar{x}\)
试图以最小支出达到既定效用的消费者也恰好需要\(\bar{x}\)
社会最优化问题就可以被分散化的机制实现
唯一性
严格拟凸
严格拟凸函数： \[ G(\theta x^a + (1 - \theta) x^b) < max(G(x^a), G(x^b)) \]
严格拟凹函数： \[ F(\theta x^a + (1 - \theta) x^b) > min(F(x^a), F(x^b)) \]
唯一性条件
考虑在约束\(G(x) \leq c\) 下最大化\(F(x)\)的问题，其中\(F\)为严格拟凹的，\(G\)为严格拟凸的。假定\(x\)满足分离角度的最优化定理，那么它将是该最优化问题的唯一解。【证明：反证法】